package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.bean.ListNode;
import zcw.com.lib_leet_code.bean.TreeNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2021/11/29.<br><br>
 *
 * 中等：序链表转换二叉搜索树
 */
public class Topic109 {

    public static void main(String[] args) {
        Topic109 instance = new Topic109();
        ListNode head;
        TreeNode root;
        int[] array;

        array = new int[] {-10, -3, 0, 5, 9};
        head = Util.createList(array);
        root = instance.sortedListToBST(head);
        Util.preTravelTree(root);
        Util.inTravelTree(root);
        Util.postTravelTree(root);
    }

    ListNode originHead;

    public TreeNode sortedListToBST(ListNode head) {
        originHead = head;
        int len = getLength(head);
        return buildTree(0, len - 1);
    }

    private int getLength(ListNode head) {
        int len = 0;

        while (head != null) {
            len++;
            head = head.next;
        }

        return len;
    }

    private TreeNode buildTree(int left, int right) {
        if(left > right) {
            return null;
        }

        int mild = (left + right + 1) / 2;
        TreeNode root = new TreeNode();
        root.left = buildTree(left, mild - 1);
        root.val = originHead.val;
        originHead = originHead.next;
        root.right = buildTree(mild + 1, right);

        return root;
    }

    public TreeNode sortedListToBST2(ListNode head) {
        return buildTree2(head, null);
    }

    private TreeNode buildTree2(ListNode left, ListNode right) {
        if(left == right) {
            return null ;
        }

        ListNode mild = helper(left, right);
        TreeNode root = new TreeNode(mild.val);
        root.left = buildTree2(left, mild);
        root.right = buildTree2(mild.next, right);
        return root;
    }

    private ListNode helper(ListNode left, ListNode right) {
        ListNode low = left;
        ListNode fast = left;

        while (fast != right && fast.next != right) {
            low = low.next;
            fast = fast.next.next;
        }

        return low;
    }
}
